home *** CD-ROM | disk | FTP | other *** search
/ The Atari Compendium / The Atari Compendium (Toad Computers) (1994).iso / files / umich / network / mail / pathalia.zoo / src / addnode.c < prev    next >
C/C++ Source or Header  |  1991-01-12  |  9KB  |  390 lines
  1. /* pathalias -- by steve bellovin, as told to peter honeyman */
  2. #ifndef lint
  3. static char    *sccsid = "@(#)addnode.c    9.6 89/05/05";
  4. #endif
  5.  
  6. #include "def.h"
  7.  
  8. #define EQ(n, s)    (*(n)->n_name == *(s) && strcmp((n)->n_name, (s)) == 0)
  9.  
  10. /* exports */
  11. node *addnode(), *addprivate();
  12. void alias(), hashanalyze(), fixprivate();
  13. node **Table;                /* hash table ^ priority queue */
  14. long Tabsize;                /* size of Table */    
  15.  
  16. /* imports */
  17. extern link *addlink();
  18. extern node *newnode(), **newtable();
  19. extern char *strsave();
  20. extern int Iflag, Tflag, Vflag;
  21. extern node **Table;
  22. extern long Ncount, Tabsize;
  23. extern char **Argv;
  24. extern void atrace(), die(), freetable();
  25. extern int strcmp();
  26.  
  27. /* privates */
  28. STATIC void crcinit(), rehash(), lowercase();
  29. STATIC long fold();
  30. STATIC long hash();
  31. STATIC node *isprivate();
  32. static node *Private;    /* list of private nodes in current input file */
  33. /*
  34.  * these numbers are chosen because:
  35.  *    -> they are prime,
  36.  *    -> they are monotonic increasing,
  37.  *    -> each is a tad smaller than a multiple of 1024,
  38.  *    -> they form a fibonacci sequence (almost).
  39.  * the first point yields good hash functions, the second is used for the
  40.  * standard re-hashing implementation of open addressing, the third
  41.  * optimizes for quirks in some mallocs i have seen, and the fourth simply
  42.  * appeals to me.
  43.  */
  44. static long Primes[] = {
  45.     1021, 2039, 3067, 5113, 8179, 13309, 21499, 34807, 56311, 0
  46. };
  47.  
  48. static int    Tabindex;
  49. static long    Tab128;        /* Tabsize * 128 */
  50.  
  51. node    *
  52. addnode(name)
  53.     register char *name;
  54. {    register long i;
  55.     register node *n;
  56.  
  57.     if (Iflag)
  58.         lowercase(name);
  59.  
  60.     /* is it a private host? */
  61.     n = isprivate(name);
  62.     if (n)
  63.         return n;
  64.  
  65.     i = hash(name, 0);
  66.     if (Table[i]) 
  67.         return Table[i];
  68.  
  69.     n = newnode();
  70.     n->n_name = strsave(name);
  71.     Table[i] = n;
  72.     n->n_tloc = i;    /* essentially a back link to the table */
  73.  
  74.     return n;
  75. }
  76.  
  77. void
  78. alias(n1, n2)
  79.     node *n1, *n2;
  80. {
  81.     link    *l;
  82.  
  83.     if (ISADOMAIN(n1) && ISADOMAIN(n2)) {
  84.         fprintf(stderr, "%s: domain alias %s = %s is illegal\n", Argv[0], n1->n_name, n2->n_name);
  85.         return;
  86.     }
  87.     l = addlink(n1, n2, (Cost) 0, DEFNET, DEFDIR);
  88.     l->l_flag |= LALIAS;
  89.     l = addlink(n2, n1, (Cost) 0, DEFNET, DEFDIR);
  90.     l->l_flag |= LALIAS;
  91.     if (Tflag)
  92.         atrace(n1, n2);
  93. }
  94.  
  95. /*
  96.  * fold a string into a long int.  31 bit crc (from andrew appel).
  97.  * the crc table is computed at run time by crcinit() -- we could
  98.  * precompute, but it takes 1 clock tick on a 750.
  99.  *
  100.  * This fast table calculation works only if POLY is a prime polynomial
  101.  * in the field of integers modulo 2.  Since the coefficients of a
  102.  * 32-bit polynomail won't fit in a 32-bit word, the high-order bit is
  103.  * implicit.  IT MUST ALSO BE THE CASE that the coefficients of orders
  104.  * 31 down to 25 are zero.  Happily, we have candidates, from
  105.  * E. J.  Watson, "Primitive Polynomials (Mod 2)", Math. Comp. 16 (1962):
  106.  *    x^32 + x^7 + x^5 + x^3 + x^2 + x^1 + x^0
  107.  *    x^31 + x^3 + x^0
  108.  *
  109.  * We reverse the bits to get:
  110.  *    111101010000000000000000000000001 but drop the last 1
  111.  *         f   5   0   0   0   0   0   0
  112.  *    010010000000000000000000000000001 ditto, for 31-bit crc
  113.  *       4   8   0   0   0   0   0   0
  114.  */
  115.  
  116. #define POLY32 0xf5000000    /* 32-bit polynomial */
  117. #define POLY31 0x48000000    /* 31-bit polynomial */
  118. #define POLY POLY31    /* use 31-bit to avoid sign problems */
  119.  
  120. static long CrcTable[128];
  121.  
  122. STATIC void
  123. crcinit()
  124. {    register int i,j;
  125.     register long sum;
  126.  
  127.     for (i = 0; i < 128; i++) {
  128.         sum = 0;
  129.         for (j = 7-1; j >= 0; --j)
  130.             if (i & (1 << j))
  131.                 sum ^= POLY >> j;
  132.         CrcTable[i] = sum;
  133.     }
  134. }
  135.  
  136. STATIC long
  137. fold(s)
  138.     register char *s;
  139. {    register long sum = 0;
  140.     register int c;
  141.  
  142.     while ((c = *s++) != 0)
  143.         sum = (sum >> 7) ^ CrcTable[(sum ^ c) & 0x7f];
  144.     return sum;
  145. }
  146.  
  147.  
  148. #define HASH1(n) ((n) % Tabsize);
  149. #define HASH2(n) (Tabsize - 2 - ((n) % (Tabsize-2)))    /* sedgewick */
  150.  
  151. /*
  152.  * when alpha is 0.79, there should be 2 probes per access (gonnet).
  153.  * use long constant to force promotion.  Tab128 biases HIGHWATER by
  154.  * 128/100 for reduction in strength in isfull().
  155.  */
  156. #define HIGHWATER    79L
  157. #define isfull(n)    ((n) * 128 >= Tab128)
  158.     
  159. STATIC long
  160. hash(name, unique)
  161.     char *name;
  162.     int unique;
  163. {    register long probe;
  164.     register long hash2;
  165.     register node *n;
  166.  
  167.     if (isfull(Ncount)) {
  168.         if (Tabsize == 0) {        /* first time */
  169.             crcinit();
  170.             Tabindex = 0;
  171.             Tabsize = Primes[0];
  172.             Table = newtable(Tabsize);
  173.             Tab128 = (HIGHWATER * Tabsize * 128L)/100L;
  174.         } else
  175.             rehash();        /* more, more! */
  176.     }
  177.  
  178.     probe = fold(name);
  179.     hash2 = HASH2(probe);
  180.     probe = HASH1(probe);
  181.  
  182.     /*
  183.      * probe the hash table.
  184.      * if unique is set, we require a fresh slot.
  185.      * otherwise, use double hashing to find either
  186.      *  (1) an empty slot, or
  187.      *  (2) a non-private copy of this host name
  188.      *
  189.      * this is an "inner loop."
  190.      */
  191.     while ((n = Table[probe]) != 0) {
  192.         if (EQ(n, name) && !(n->n_flag & ISPRIVATE) && !unique)
  193.             return probe;    /* this is it! */
  194.  
  195.         probe -= hash2;        /* double hashing */
  196.         if (probe < 0)
  197.             probe += Tabsize;
  198.     }
  199.     return probe;                    /* brand new */
  200. }
  201.  
  202. STATIC void
  203. rehash()
  204. {    register node **otable, **optr;
  205.     register long probe;
  206.     long osize;
  207.  
  208. #ifdef DEBUG
  209.     hashanalyze();
  210. #endif
  211.     optr = Table + Tabsize - 1;    /* ptr to last */
  212.     otable = Table;
  213.     osize = Tabsize;
  214.     Tabsize = Primes[++Tabindex];
  215.     if (Tabsize == 0)
  216.         die("too many hosts");    /* need more prime numbers */
  217.     vprintf(stderr, "rehash into %d\n", Tabsize);
  218.     Table = newtable(Tabsize);
  219.     Tab128 = (HIGHWATER * Tabsize * 128L)/100L;
  220.  
  221.     do {
  222.         if (*optr == 0)
  223.             continue;    /* empty slot in old table */
  224.         probe = hash((*optr)->n_name,
  225.             ((*optr)->n_flag & ISPRIVATE) != 0);
  226.         if (Table[probe] != 0)
  227.             die("rehash error");
  228.         Table[probe] = *optr;
  229.         (*optr)->n_tloc = probe;
  230.     } while (optr-- > otable);
  231.     freetable(otable, osize);
  232. }
  233.  
  234. void
  235. hashanalyze()
  236. #if 0
  237. {     long    probe, hash2;
  238.     int    count, i, collision[8];
  239.     int    longest = 0, total = 0, slots = 0, longprobe = 0;
  240.     int    nslots = sizeof(collision)/sizeof(collision[0]);
  241.  
  242.     if (!Vflag)
  243.         return;
  244.  
  245.     strclear((char *) collision, sizeof(collision));
  246.     for (i = 0; i < Tabsize; i++) {
  247.         if (Table[i] == 0)
  248.             continue;
  249.         /* private hosts too hard to account for ... */
  250.         if (Table[i]->n_flag & ISPRIVATE)
  251.             continue;
  252.         count = 1;
  253.         probe = fold(Table[i]->n_name);
  254.         /* don't change the order of the next two lines */
  255.         hash2 = HASH2(probe);
  256.         probe = HASH1(probe);
  257.         /* thank you! */
  258.         while (Table[probe] != 0
  259.             && strcmp(Table[probe]->n_name, Table[i]->n_name) != 0) {
  260.             count++;
  261.             probe -= hash2;
  262.             if (probe < 0)
  263.                 probe += Tabsize;
  264.         }
  265.         if (Table[probe] == 0)
  266.             die("impossible hash error");
  267.         
  268.         total += count;
  269.         slots++;
  270.         if (count > longest) {
  271.             longest = count;
  272.             longprobe = i;
  273.         }
  274.         if (count >= nslots)
  275.             count = 0;
  276.         collision[count]++;
  277.     }
  278.     for (i = 1; i < nslots; i++)
  279.         if (collision[i])
  280.             fprintf(stderr, "%d chains: %d (%ld%%)\n",
  281.                 i, collision[i], (collision[i] * 100L)/ slots);
  282.         if (collision[0])
  283.             fprintf(stderr, "> %d chains: %d (%ld%%)\n",
  284.                 nslots - 1, collision[0],
  285.                 (collision[0] * 100L)/ slots);
  286.     fprintf(stderr, "%2.2f probes per access, longest chain: %d, %s\n",
  287.         (double) total / slots, longest, Table[longprobe]->n_name);
  288.     if (Vflag < 2)
  289.         return;
  290.     probe = fold(Table[longprobe]->n_name);
  291.     hash2 = HASH2(probe);
  292.     probe = HASH1(probe);
  293.     while (Table[probe] != 0
  294.         && strcmp(Table[probe]->n_name, Table[longprobe]->n_name) != 0) {
  295.         fprintf(stderr, "%5d %s\n", probe, Table[probe]->n_name);
  296.         probe -= hash2;
  297.         if (probe < 0)
  298.             probe += Tabsize;
  299.     }
  300.     fprintf(stderr, "%5d %s\n", probe, Table[probe]->n_name);
  301.     
  302. }
  303. #else
  304. {
  305.     /* the hash algorithms are perfect -- leave them alone */
  306. }
  307. #endif
  308.  
  309. /* convert to lower case in place */
  310. STATIC void
  311. lowercase(s)
  312.     register char *s;
  313. {
  314.     do {
  315.         if (isupper(*s))
  316.             *s -= 'A' - 'a';    /* ASCII */
  317.     } while (*s++);
  318. }
  319.  
  320. /*
  321.  * this might need change if privates catch on
  322.  */
  323. STATIC node *
  324. isprivate(name)
  325.     register char *name;
  326. {    register node *n;
  327.  
  328.     for (n = Private; n != 0; n = n->n_private)
  329.         if (strcmp(name, n->n_name) == 0)
  330.             return n;
  331.     return 0;
  332. }
  333.  
  334. /*  Add a private node so private that nobody can find it.  */
  335. node *
  336. addhidden(name)
  337.     register char *name;
  338. {    register node *n;
  339.     register int i;
  340.     if (Iflag)
  341.         lowercase(name);
  342.  
  343.     n = newnode();
  344.     n->n_name = strsave(name);
  345.     n->n_flag = ISPRIVATE;
  346.     i = hash(n